В этом параграфе мы поговорим о регуляризации, но использовать мы её будем не для стабилизации обучения, а для того, чтобы накладывать ограничение на получаемое нами решение. Чтобы отличать их от стабилизирующих слагаемых, для таких регуляризаторов будем использовать обозначение $\psi_t(w)$

В теории от регуляризатора требуется только выпуклость, но на практике широко используются лишь три вида:

• $L_1 = \vert\vert w\vert\vert_1$ и его собрат $L_{1/2}$;
• $L_2 = \vert\vert w\vert\vert_2^2$;
• Проекция на выпуклое множество $\chi$:

$$\psi(w) = I_{\chi}(w) = \begin{cases} \infty & w \not\in \chi \\ 0 & w \in \chi \end{cases}$$

Классическим способом введения регуляризации является прибавление к оптимизируемому функционалу:

$$\hat{f}_t(w) = f_t(w) + \psi_t(w)$$

с последующим применением любых методов оптимизации «из коробки». Яркий пример — $L_2$ регуляризация:

$$\hat{f}_t(w) = f_t(w) + \frac{1}{2\lambda_2}\vert\vert w\vert\vert_2^2,$$

которая не портит гладкости функционала.

Идея неразложения регуляризаторов в субградиентную оценку

Вспомним вывод linearized FTRL. В ходе линеаризации мы заменяли все функции $\hat{f}_t(w)$ на их субградиентную оценку в точке $w_t$. Для регуляризованного функционала $\hat{f}_t(w) = f_t(w) + \psi_t(w)$ получалась бы такая оценка:

$$\hat{f}_t(w) \geq \hat{f}_t(w_t) + (g_t + \partial\psi_t)^T (w - w_t),$$

где через $\partial\psi_t$ мы обозначили для краткости субградиент $\psi_t$ в точке $w_t$. Теперь субградиентную оценку можно подставить в метод FTRL:

$$w_{t+1} = arg\min\limits_w \Big[(g_{1:t} + \partial\psi_{1:t})^Tw + \sum\limits_{s=1}^t\vert\vert w - w_s\vert\vert_{\sigma_s}^2\Big]$$

Идея неразложения состоит в следующем: заменим на субградиентную оценку только $f_t(w)$, а регуляризатор будем подбирать так, чтобы задача FTRL решалась аналитически. Интуитивно, оценка

$$\hat{f}_t(w) = f_t(w) + \psi_t(w) \geq f_t(w_t) + g_t^T(w - w_t) + \psi_t(w)$$

должна быть точнее оценки

$$\hat{f}_t(w) = f_t(w) + \psi_t(w) \geq f_t(w_t) + \psi_t(w_t) + (g_t + \partial\psi_t)^T (w - w_t)$$

а значит, и метод оптимизации будет точнее и эффективнее.

Эта идея очень важна для построения регуляризованных алгоритмов онлайн-обучения.

Давайте выпишем, как будут выглядеть с учётом этой идеи регуляризованные алгоритмы.

Composite Objective FTRL

$$w_{t+1} = arg\min\limits_w \Big[g_{1:t}^Tw + \psi_{1:t}(w) + \sum\limits_{s=1}^t\vert\vert w - w_s\vert\vert_{\sigma_s}^2\Big]$$

Online Mirror Descent, Proximal Gradient Descent, (F)ISTA

$$w_{t+1} = arg\min\limits_w \Big[g_t^Tw + \psi_t(w) + \vert\vert w - w_t\vert\vert_{\sigma_t}^2 \Big]$$

Напомним, что три названия в заголовке соответствуют трём способам восприятия этой формулы:

• Online Mirror Descent — метод онлайн-обучения;
• Proximal Gradient Descent — метод (стохастической) батч-оптимизации. В стохастическом случае он неотличим от Mirror Descent;
• (F)ISTA — по сути, это название аналитического решения указанного уравнения для $L_1$-регуляризации.

Связь между Composite-Objective FTRL и Proximal Gradient Descent. Lazy vs Greedy представления

В этом подразделе мы будем проводить рассуждения на примере $L_1$-регуляритора. для других регуляризаторов выкладки будут аналогичными.

Выпишем Proximal (он же Mirror) Gradient Descent с $L_1$-регуляризацией:

$$w_{t+1} = arg\min\limits_w g_t^Tw + \lambda_1\vert\vert w\vert\vert_1 + \frac{1}{2\eta_t}\vert\vert w - w_t\vert\vert_2^2$$

Необходимым условием минимума явняется равенство нулю градиента (а в данном случае субградиента) всего выражения:

$$0 = g_t + \hat{g}_t + \frac{1}{\eta_t}(w_{t+1} - w_t)$$

где $\hat{g}_t$ - субградиент регуляризатора $\lambda_1\vert\vert w\vert\vert_1$ в точке $w_{t}$. Отсюда получаем

$$w_{t+1} = w_{t} - \eta_t (g_t + \hat{g}^T)$$

Если же переписать формулы в духе FTRL, мы получим

$$w_{t+1} = arg\min\limits_{w} g_{1:t}^Tw + \hat{g}_{1:{t-1}}^Tw + \lambda \vert\vert w\vert\vert_1 + \frac{1}{2}\sum\limits_{s=0}^t\vert\vert w-w_s\vert\vert_{\sigma_s}^2$$

Получился метод, который оптимизирует $L_1$-регуляризатор в явном виде только на текущей итерации $t$, а для остальных использует субоптимальные субградиентные оценки. Заметим, что тем же выражением можно ограничить сверху и функционал:

$$w_{t+1} = arg\min\limits_{w} g_{1:t}^Tw + t\lambda \vert\vert w\vert\vert_1 + \frac{1}{2}\sum\limits_{s=0}^t\vert\vert w-w_s\vert\vert_{\sigma_s}^2$$

Мы получили метод FTRL с incremental $L_1$ — более сильным и стабильным вариантом регуляризации, чем Mirror Descent. Подробнее его анализом мы займемся в параграфе про продвинутую $L_1$-регуляризацию.

$L_1$-регуляризация

Отбор параметров разреженных моделей

Предположим, что мы хотим обучить модель минимального размера и при этом как можно лучшего качества. В этом нам поможет отбор параметров. А именно, давайте постараемся оставить только те из них, которые оказывают наиболее влияние на лосс $f_{1:T}(w)$.

Определение. Будем называть параметр $w_i$ разреженным, если он не используется (пропускается) при предсказании некоторых $f_t(w)$. «Некоторых» может означать как десятую часть, так и $0.99999$ прогнозов $f_t(w)$, главное — что такие объекты просто есть. Частым мы будем называть параметр, у которого частота пропусков низкая (например, $10\%$ пропусков), а редким — тот, у которого она высокая (второй случай).

Пример. Рассмотрим модель разреженной линейной регрессии $f_t(w) = (w^Tx_t - y_t)^2$. Обычно она применяется в ситуациях, когда элементы вектора признаков $x_{t,i}$ — это $0$ или $1$ (например, «встретилось ли $i$-е слово в $t$-м документе»), причем на практике доля единиц обычно бывает очень маленькой. Поэтому существенная часть параметров $w_i$ при прогнозе на шаге $t$ будет умножаться на нули и, таким образом, не будет использоваться.

Обратите внимание: как правило, в литературе по онлайн-обучению говорят о разреженных параметрах, а не признаках. Впрочем, подавляющее большинство моделей на разреженных признаках устроены так, что каждому такому признаку сопоставляется некий набор параметров, поэтому определения «разреженный признак» и «разреженные параметры» взаимозаменяемы. В линейной модели, как в примере выше, каждому признаку $x_i$ сопоставляется параметр $w_i$. В более сложных моделях признаку $x_i$ может сопоставляться вектор параметров $w_i$ — эмбеддинг этого признака.

Давайте теперь поймём, что означает фраза «признак влияет на лосс $f_{1:T}(w)$». Оказывать влияние можно двумя способами:

1. Качеством. Если параметр $w_i$ редкий, но очень хорошо прогнозирует свой небольшой набор объектов, его стоит оставить. За счет того, что мы оставим достаточное количество таких параметров, мы можем покрыть большое число объектов. Такие параметры называются memorization parameters (они как будто запоминают «свои» объекты).
2. Количеством. Если параметр $w_i$ часто встречается, то он в любом случае должен остаться в модели и помогать с суммарным качеством прогноза.

Убирать мы хотим только слабые и редкие параметры. Таких, как правило, больше $99\%$.

Обратите внимание: мы не хотим убирать слабые, но часто встречающиеся параметры. Тому есть две причины:

1. Места они много не занимают, а количества данных в large scale задачах достаточно, чтобы правильно выучить эти параметры. Они будут вносить свой, пусть и небольшой, вклад в общее качество;
2. Частые параметры хорошо запоминают среднее поведение на всех данных, а разреженные — поведение на конкретных объектах. Если наша цель — оставить как можно меньше параметров, то выгоднее хорошо выучить среднее поведение на всех данных, а отклонения от среднего запомнить с помощью memorization parameters. Если в модели есть только супер-разреженные параметры, то из-за огромной вариативности в их возможных комбинациях в данных каждому параметру придется доучивать среднее поведение. Подробнее на этой проблеме мы остановимся в конце параграфа.

Инициализация разреженных параметров

В обучении разреженных моделей все параметры, на которые накладывается $L_1$-регуляризация, инициализируются нулями. С точки зрения здравого смысла такая инициализация довольно естественна, однако есть и более формальное обоснование;

1. Если параметры инициализируются нулями, то мы по мере обучения смотрим на градиенты этих параметров и в зависимости от градиентов принимаем решение, нужен нам параметр для прогноза или не нужен. Все параметры стартуют в равных условиях, и модель понемногу выходит из состояния «абсолютная разреженность», выучивая что-то содержательное.
2. Если же параметры инициализируются случайно, то нам надо сначала доучить все параметры до какого-то более или менее разумного значения, а потом уже пытаться понять, нужен ли он нам. Момент, когда модель начинает эффективно разреживаться, тем самым очень сильно отдалается.

Composite-objective FTRL с $L_1$-регуляризацией

Напомним формулировку задачи:

$$w_{t+1} = arg\min\limits_w g_{1:t}^Tw + \lambda_{1,t}\vert\vert w\vert\vert_1 + \frac{1}{2}\sum\limits_{s=1}^T\vert\vert w - w_s\vert\vert_{\sigma_s}^2$$

Решение можно выписать в явном виде. Для этого введём следующие обозначения:

• $z_t$ будет аккумулировать сумму градиентов, $z_0 = 0$,
• $n_t$ будет аккумулировать сумму поэлементных квадратов градиентов, $n_0 = 0$,
• $\alpha$ — это learning rate.

Следующие формулы выписаны отдельно для каждой координаты. В них $i$ — индекс параметра модели, $t$ — номер итерации.

$$\sigma_{t,i} = \frac{1}{\eta_{t,i}} - \frac{1}{\eta_{t-1,i}} = \frac{1}{\alpha}\Big(\sqrt{n_{t,i} + g_{t,i}^2} - \sqrt{n_{t,i}}\Big)$$

$$z_{t+1,i} = z_{t,i} + g_{t,i} - \sigma_{t,i}w_{t,i}$$

$$n_{t+1,i} = n_{t,i} + g_{t,i}^2$$

$$w_{t+1,i} = \begin{cases} 0 & \vert z_{t+1,i}\vert \leq \lambda_{1,t}\\ -\frac{\alpha}{\sqrt{n_{t+1,i}} + \alpha\lambda_{2,t}} \Big(z_{t+1,i} - sgn(z_{t+1,i})\lambda_{1,t} \Big) & \vert z_{t+1,i}\vert > \lambda_{1,t} \end{cases}\qquad(\ast)$$

Вывод этих формул хорошо расписан в конспекте курса Д. А. Кропотова.

Анализ аналитического решения

При регуляризаторе $\vert\vert w\vert\vert_1$ в оптимизируемом функционале стоят коэффициенты $\lambda_{1,t}$, которые могут как-то зависеть от $t$. Обычно рассматривают три вида зависимости:

1. Fixed: $\lambda_{1,t} = \lambda$.
2. Squared incremental: $\lambda_{1,t} = \sqrt{t}\lambda$
3. Linear incremental: $\lambda_{1,t} = t\lambda$

Их также можно комбинировать, получая коэффициенты регуляризации

$$\lambda_{1,t} = \lambda_{1,global} + \sqrt{t}\lambda_{1,sqrt} + t\lambda_{1,incremental}$$

Напомним, что все веса $w_{i}$ мы инициализируем нулями. По формулам $(\ast)$ из нуля на шаге $t$ выводятся веса $w_i$, для которых

$$\vert g_{1:t,i} - \sum\limits\sigma_sw_{s,i}\vert > \lambda_{1,t}.$$

Таким образом, начальное условие выхода параметров из нуля имеет вид

$$\vert g_{1:t,i}\vert > \lambda_{1,t}.$$

Попробуем понять физический смысл этого неравенства.

Напоминание. Говорят, что функция $f(w)$ имеет липшиц-непрерывный градиент с константой $L$, если

$$\vert\vert \nabla f(x) - \nabla f(y)\vert\vert_2^2 \leq \frac{L}{2} \vert\vert x - y\vert\vert_2^2$$

Предположим, что это выполняется (ниже мы покажем, что это не слишком обременительное ограничение). Тогда, подставив в качестве $y$ точку оптимума функции $f_t(w)$ (не путайте с глобальным $w_T^*$ из regret!), мы получим

$$\vert\vert \nabla f(x)\vert\vert_2^2 \leq \frac{L}{2}\vert\vert x - x_*\vert\vert_2^2$$

Это означает, что для достаточно хорошей функции норма градиента является оценкой снизу на расстояние до точки оптимума в пространстве параметров. Чем больше норма градиента, тем дальше мы от оптимальных параметров $w$.

Вернемся к выражению $\vert g_{1:t,i}\vert > \lambda_{1,t}$. Здесь мы имеем дело (а) отдельно с каждой из координат и (б) с нормой суммы градиентов (а не с суммой норм). Хорошая новость: утверждение выше верно и для функций одной переменной, то есть $\vert g_{s,i}\vert$, грубо говоря, показывает, насколько мы далеки от оптимума по $i$-й координате. Знак $g_{s,i}$ говорит о том, в какую сторону мы будем сдвигаться по $i$-й координате $w$ на $s$-м шаге. Если сдвиги были в основном в одну сторону, то $g_{1:t,i}$ будет больше, а если они всё время в разную сторону, то отдельные слагаемые могут скомпенсировать друг друга, и $g_{1:t,i}$ может быть малым.

Отметим ещё, что абсолютная величина компоненты $g_{1:t,i}$ на первых итерациях может отражать прогнозирующую силу параметра $w_i$: в самом деле, неверное значение важного для предсказания параметра может вести к большим ошибкам, что будет давать большие градиенты.

Посмотрим теперь, как будет вести себя разреженная модель в зависимости от вида $\lambda_{1,t}$.

Linear incremental ($\lambda_{1,t} = t\lambda_1$)

Условие выхода $w_i$ из нуля принимает вид

$$\vert g_{1:t,i}\vert > t\lambda_1,$$

что равносильно

$$\left| \frac{1}{t}g_{1:t,i}\right| > \lambda_1$$

Ограничение на среднее значение компоненты градиента означает, что для выхода из нуля параметр $w_i$ должен иметь определённую прогнозирующую силу. Это противоречит нашему требованию о том, чтобы частые маломощные параметры все равно присутствовали в модели и выучивали среднее поведение.

Обратите внимание. Выше мы показали, что проксимальный градиентный спуск с обычным $L_1$

$$w_{t+1} = arg\min\limits_w g_t^Tw + \lambda_1 \vert\vert w\vert\vert_1 + \frac{1}{\eta_t}\vert\vert w - w_t\vert\vert_2^2$$

в некотором смысле эквивалентен Composite-Objective FTRL с инкрементальным $L_1$. Таким образом, обычная $L_1$-регуляризация в классическом градиентном спуске эквивалентна именно инкрементальному $L_1$, который, как мы выяснили, субоптимален. Ниже мы рассмотрим специфический для FTRL вариант $L_1$-регуляризации, который лишен этих недостатков.

Фиксированный ($\lambda_{1,t} = t\lambda_1$)

Это самый мощный и полезный на практике режим.

Здесь мы не нормируем на $\frac{1}{t}$ (то есть не берём среднее), и это означает, что выйти из нуля может и слабый, но частый параметр, который за много итераций накопит достаточно большую сумму частных производных.

Свойства фильтрации с фиксированным регуляризатором в точности совпадают с продуктовыми требованиями:

1. Редкий параметр с мощной прогнозирующей силой на старте будет иметь большие по модулю градиенты одного знака, и он выйдет из нуля;
2. Редкий параметр с малой прогнозной силой не выйдет из нуля;
3. Частые параметры в любом случае выйдут из нуля.

Squared incremental: ($\lambda_{1,t} = \sqrt{t}\lambda$)

В этой статье было теоретически обосновано, что если параметр частый, но нерелевантный и абсолютно шумный, то дисперсия $\vert g_{1:t}\vert$ будет иметь асимптотику $O(\sqrt{t})$. Из этого следует, что, если сделать регуляризацию порядка $\sqrt{t}$, мы лишим такой случайный шум почти любых шансов выйти из нуля.

К сожалению, ни в игрушечных примерах вроде Avazu, ни в продакшен задачах улучшений качества прогноза или степени разреживания модели без потери качества достичь не удалось. Возможно, вам повезет больше.

Полезность частых параметров для разреживания модели

Рассмотрим две линейных модели

$$f_t(w) = w^Tx_t + b,\quad g_t(w) = w^Tx_t,$$

в которых все параметры $w_i$ разреженные. Давайте считать, что в первой модели есть константный (и совсем даже не разреженный) признак $x_b = 1$, которому и соответствует параметр $b$.

Теперь в каждой из моделей наложим на $w$ регуляризацию $L_1$ и сравним, что получится:

1. В модели $f_t$ параметрам $w_i$ нужно запомнить «отклонение» от среднего $b$;
2. В модели $g_t$ параметрам $w_i$ нужно запомнить абсолютное значение предсказания.

Нетрудно понятно, что при наличии bias нормы градиентов в первой модели в среднем будут намного меньше, потому что мы на каждом шаге оптимизации будем стартовать с точки, которая в среднем ближе к точке оптимума (bias и есть наше среднее). Поэтому меньше весов смогут преодолеть порог по модулю суммы градиентов и выйти из нуля. Таким образом, несмотря на одинаковый оптимум без регуляризации, при введении $L_1$-регуляризации модель с bias будет обладать более хорошим соотношением разреженность/качество прогноза.

Эта логика легко обобщается на более сложные случаи, когда вместо bias у нас есть неразреженные контентные признаки. Вывод такой: модели, в которых есть только очень разреженные параметры, обладают гораздо худшим соотношением разреженность/качество, чем модели, в которых есть и контентные, и разреженные параметры.

Убедиться в этих эффектах мы сможем в разделе с практикой на линейных моделях.

$L_2$ регуляризация

Weight decay

Рассмотрим обыкновенный SGD.

$$w_{t+1} = w_t - \alpha g_t$$

Weight decay состоит во введение штрафа на размер текущих весов:

$$w_{t+1} = (1 - \lambda)w_t - \alpha g_t,\quad 0 \leq \lambda < 1$$

Внимательные читатели уже заметили, что в случае с SGD это эквивалентно введению $L_2$-регуляризации. Давайте разберёмся, как это сделать правильно.

Decoupled weight decay

Попробуем заменить $f_t(w)$ на

$$\hat{f}_t(w) = f_t(w) + \lambda_2 \vert\vert w\vert\vert_2^2$$

и запустить любой адаптивный метод, например, AdaGrad. Если мы беспечно заменим на градиентную оценку всю функцию $\hat{f}_t(w)$ (забыв, что с регуляризатором этого делать не стоит), то алгоритм примет вид

$$w_{t+1} = w_t - \hat{\eta}_tg_t,$$

где

$$\hat{\eta}_t = \frac{\alpha}{\sqrt{\sum\limits_{s=1}^t (g_s + \lambda_2 w_s)^2 }}$$

В этих формулах нехороши две вещи:

1. Коэффициенты $\alpha$ и $\lambda_2$ нетривиальным образом взаимодействуют. Это крайне неудобно при переборе гиперпараметров: изменение learning rate $\alpha$ должно влечь за собой переподбор коэффициента регуляризации $\lambda_2$ по полной сетке;
2. В квадратах градиентов мы хотим видеть только адаптивность к кривизне самой функции $f_t$, но теперь там ещё добавка $\lambda_2w_s$.

Эта проблема была впервые замечена в Decoupled weight decay regularization. Авторы также рассматривали влияние на momentum, к этому мы вернёмся в параграфе про AdamW.

Авторы статьи предлагают модифицировать метод AdaGrad следующим образом:

$$w_{t+1} = w_t - \frac{\alpha}{\sqrt{\sum\limits_{s=1}^t g_s^2}} g_t - \lambda_2 w_t$$

Сразу отметим сходство с исходными формулами weight decay — его и добивались авторы.

Decoupled weight decay — это адаптивный $L_2$

Легко видеть, что формула

$$w_{t+1} = w_t - \frac{\alpha}{\sqrt{\sum\limits_{s=1}^t g_s^2}} g_t - \lambda_2 w_t$$

описывает обыкновенный покоординатный градиентный спуск с некоторым линеаризованным $L_2$-регуляризатором. Давайте «проинтегрируем» это выражение обратно до аргминимума, из которого бы получились такие формулы обновления весов:

$$w_{t+1} = arg\min\limits_w \Big[ g_t^Tw + \frac{\lambda_2}{\eta_t}\color{#E06A27}{w_t^T}w + \frac{1}{2\eta_t}\vert\vert w - w_t\vert\vert_2^2 \Big]$$

Получается, что decoupled weight decay — это адаптивный $L_2$-centered регуляризатор. Его можно усовершенствовать, вспомним наше важное правило не заменять регуляризатор на субградиентную оценку. Перейдём к задаче

$$w_{t+1} = arg\min\limits_w \Big[ g_t^Tw + \frac{\lambda_2}{2\eta_t}\vert\vert w\vert\vert_2^2 + \frac{1}{2\eta_t}\vert\vert w - w_t\vert\vert_2^2 \Big]$$

Она отличается от предыдущей заменой $\color{#E06A27}{w_t^T}w$ на $\color{#348FEA}{w^T}w = \vert\vert w\vert\vert^2$. Её решение имеет вид

$$w_{t+1} = \color{#C81D6B}{\frac{1}{1 + \lambda_2}}\Big(w_t - \eta_t g_t \Big)$$

Поскольку мы меньше огрубляем оптимизируемый функционал, обучение может стать немного стабильнее.

Обратите внимание, что в оптимизационной задаче у нас теперь стоит не просто $\lambda_2$, а $\frac{\lambda_2}{2\eta_t}$.

Decoupled $L_2$-регуляризация в Composite-Objective FTRL

Теперь посмотрим, как decoupled weight decay будте работать с Composite-Objective FTRL. Линеаризованная задача имеет вид:

$$w_{t+1} = arg\min\limits_w \left[g_{1:t}^Tw + \frac{\lambda_2}{2}\vert\vert w\vert\vert_{\sigma_{1:s}}^2 + \frac{1}{2}\sum\limits_{s=1}^t\vert\vert w - w_s\vert\vert_{\sigma_s}^2\right]$$

Перепишем её:

$$w_{t+1} = arg\min\limits_w \left[g_{1:t}^Tw + \frac{1}{2}\sum\limits_{s=1}^t\Big(\vert\vert w - w_s\vert\vert_{\sigma_s}^2 + \lambda_2\vert\vert w\vert\vert_{\sigma_s}^2 \Big)\right]$$

Нетрудно показать, что решение имеет вид

$$z_{t+1} = z_t + g_t - \sigma_t\odot w_t,$$

$$w_{t+1} = -\color{#C81D6B}{\frac{1}{1 + \lambda_2}} \frac{1}{\eta_t}z_t.$$

Для $z_t$ можно написать и явную формулу: $z_{t} = g_{1:t} - \sum_{s=1}^t\sigma_s\odot w_s$.

Замечание. Чтобы оценить Regret такого метода, мы не сможем механически воспользоваться оценкой для AdaGrad: ведь она базированась на оценке на Regret, выведенной либо для целиком Proximal, либо для целиком Centered $L_2$-регуляризаторов. Composite objective из теоремы 10 тут не годится, так как Centered регуляризатор в этом случае не поедет в оценку норм градиентов, а мы в текущем представлении рассматриваем Proximal и Centered как равноправные члены. Интуитивно, мы должны применить Lemma 7 к обоим регуляризаторам и получить точно такую же оценку с такой же двойственной нормой (напомним, что centered и proximal регуляризаторы имеют одинаковую двойственную норму). Двойственная норма такая же -> формулы оптимального метода AdaGrad будут такие же. Мы оставляем это читателям в качестве упражнения.

$I_{\chi}(w)$: проекция на выпуклое множество $\chi$

Напоминание: множество $\chi$ называется выпуклым, если

$$\forall x,y\in \chi,\ \forall\alpha \in [0; 1]: \quad \alpha x + (1-\alpha)y \in \chi$$

Проекцией на это множество называют функцию

$$I_{\chi}(w) = \begin{cases} \infty & w \not\in \chi \\ 0 & w \in \chi \end{cases}$$

Докажем, что $I_{\chi}(w)$ — выпуклый регуляризатор. Для этого нам нужно проверить неравенство

$$\alpha I(x) + (1-\alpha)I(y) \geq I(\alpha x + (1 - \alpha) y).$$

Единственный шанс, когда это может быть нарушено — это $I(\alpha x + (1 - \alpha) y) = \infty$, $I(x) = 0$, $I(y) = 0$. Это значит, что $x,y\in \chi$, а $\alpha x + (1 - \alpha) y \notin \chi$, что противоречит выпуклости $\chi$.

Вернемся к формулам FTRL. Здесь ситуация сильно проще — от накидывания любых последовательностей $\alpha_{1:T}$ на регуляризатор ничего не изменится, так что его всегда оставляют просто as is

$$w_{t+1} = arg\min\limits_w g_{1:t}^Tw + I_{\chi}(w) + \frac{1}{2}\sum\limits_{s=1}^T\vert\vert w - w_s\vert\vert_{\sigma_s}^2$$

Аналитические решения для каждого вида $\chi$ нужно искать отдельно. Примерно все решения получаются путем выноса $I_{\chi}(w)$ из оптимизируемого функционала и превращения его в ограничение, после чего можно применить метод множителей Лагранжа.

Проекция на шар ${x: \vert\vert x\vert\vert \leq c}$

Решим аналитически задачу проекции на шар

$$\begin{cases} g_{1:t}^Tw + \frac{1}{2}\sum\limits_{s=1}^T\vert\vert w - w_s\vert\vert_{\sigma_s}^2\longrightarrow\min_w,\\ \vert\vert w\vert\vert_2 \leq c. \end{cases}$$

Функция Лагранжа будет иметь вид

$$L(w, \lambda) = g_{1:t}^Tw + \frac{1}{2}\sum\limits_{s=1}^T\vert\vert w - w_s\vert\vert_{\sigma_s}^2 + \lambda(\vert\vert w\vert\vert_2 - c),$$

а её градиент равен

$$\nabla_wL(w, \lambda) = g_{1:t}^T + \sum\limits_{s=1}^T(w - w_s)\odot\sigma_s + \lambda \frac{w}{\vert\vert w\vert\vert_2},$$

где $\sigma_s$ - вектор, а $\odot$ — поэлементное умножение векторов. Приравнивая к нулю градиент, получаем

$$z_t + \sigma_{1:s}\odot w + \lambda \frac{w}{\vert\vert w\vert\vert_2} = 0,$$

где мы, как обычно, обозначили $z_{t} = g_{1:t} - \sum_{s=1}^t\sigma_s\odot w_s$.

Проанализируем условие дополняющей нежесткости $\lambda(\vert\vert w\vert\vert -c) = 0$. Если $\lambda = 0$, то решение $w$ уже находится внутри шара и имеет вид

$$w = \frac{-z_t}{\sigma_{1:s}}$$

При практической реализации мы просто сначала посчитаем это выражение и проверим, не попадаем ли мы в шар. Если попадаем — отлично, если нет — то дальше говорим, что $\vert\vert w\vert\vert = c$ и решаем продолжаем решение

$$z_t + \sigma_{1:s}*w + \lambda \frac{w}{с} = 0$$

$$w = \frac{-z_t}{\sigma_{1:s} + \frac{\lambda}{c}}$$

Теперь подставим это в $\vert\vert w\vert\vert = c$ и получим

$$\vert\vert w\vert\vert = \frac{\vert\vert z_t\vert\vert }{\sigma_{1:s} + \frac{\lambda}{c}} = c$$

$$\lambda = \vert\vert z_t\vert\vert - \sigma_{1:s}c$$

$$w = c\frac{-z_t}{\vert\vert z_t\vert\vert }$$

Получаем, что если мы находимся внутри шара, то мы действуем согласно обыкновенному adaptive алгоритму со всеми хорошими свойствами, иначе — проекция побеждает.

Аналогично $L_1$ регуляризации, здесь тоже есть различия между lazy и greedy представлением этого регуляризатора. Однако, в классических DL задачах эти методы встречаются не слишком часто и здесь сложно привести какой-нибудь значимый успех, который мог бы улучшить качество в важной задача. Навскидку мы можем вспомнить разве что Adversatial White-Box learning, в котором можно было бы это попробовать.